package com.hoppinzq.algorithm.linear;

import com.hoppinzq.algorithm.linear.interfs.MyList;

import java.util.Iterator;

/**
 * 双向链表，跟单向链表一样
 * 在查找或修改时执行效率低，时间复杂度是O(n)
 * 在添加或删除时执行效率高，时间复杂度是O(1)，且扩容方便
 * 每个节点都有一个前驱和后继
 * 只能顺序存取
 * @param <T>
 */
public class MyShuangLinkedList<T> implements MyList<T>,Iterable<T>{
    //头节点
    private Node head;
    //尾节点
    private Node last;
    //长度
    private int N;

    /**
     * 内部节点类 ，结构：前驱+数据+后继
     */
    public class Node{
        private Node prev;
        private Node next;
        private T data;

        public Node(Node prev, Node next, T data) {
            this.prev = prev;
            this.next = next;
            this.data = data;
        }
    }

    /**
     * 构造方法
     */
    public MyShuangLinkedList() {
        head=new Node(null,null,null);
        last=null;
        N=0;
    }

    /**
     * 清空双链表
     */
    @Override
    public void clear() {
        head.next=null;
        last=null;
        N=0;
    }

    /**
     * 判空
     * @return
     */
    @Override
    public boolean isEmpty() {
        return N==0;
    }

    /**
     * 返回链表长度
     * @return
     */
    @Override
    public int length() {
        return N;
    }

    /**
     * 获取头节点
     * @return
     */
    public T getFirst(){
        if (isEmpty()){
            return null;
        }
        return head.next.data;
    }

    /**
     * 获取尾节点
     * @return
     */
    public T getLast(){
        if (isEmpty()){
            return null;
        }
        return last.data;
    }

    /**
     * 获取第i个节点的数据
     * @param i
     * @return
     */
    @Override
    public T get(int i) {
        Node node=head.next;
        for(int index=0;index<i;index++){
            node=node.next;
        }
        return node.data;
    }

    /**
     * 追加节点
     * @param t
     */
    @Override
    public void insert(T t) {
        if(N==0){
            Node newNode=new Node(head,null,t);
            last=newNode;
            head.next=last;
        }else{
            Node node=head;
            for(int i=0;i<N;i++){
                node=node.next;
            }
            Node newNode=new Node(node,null,t);
            node.next=newNode;
            last=newNode;
        }
        N++;
    }

    /**
     * 指定位置插入节点
     * @param i
     * @param t
     */
    @Override
    public void insert(int i, T t) {
        Node node=head;
        for(int index=0;index<i;index++){
            node=node.next;
        }
        Node next=node.next;
        Node newNode=new Node(node,next,t);
        node.next=newNode;
        next.prev=newNode;
        N++;
    }

    /**
     * 移除指定位置的节点
     * @param i
     * @return
     */
    @Override
    public T remove(int i) {
        Node node=head;
        for(int index=0;index<i;index++){
            node=node.next;
        }
        Node curr=node;
        Node prev=curr.prev;
        Node next=curr.next;
        prev.next=next;
        next.prev=prev;
        N--;
        return curr.data;
    }

    /**
     * 返回指定数据所在的节点的索引，没有匹配返回-1
     * @param t
     * @return
     */
    @Override
    public int indexOf(T t) {
        Node node=head;
        for(int i=0;i<N;i++){
            node=node.next;
            if(node.data.equals(t)){
                return i;
            }
        }
        return -1;
    }

    @Override
    public Iterator<T> iterator() {
        return new TIterator();
    }

    private class TIterator implements Iterator{
        private Node n;
        public TIterator(){
            this.n=head;
        }
        @Override
        public boolean hasNext() {
            return n.next!=null;
        }

        @Override
        public Object next() {
            n=n.next;
            return n.data;
        }
    }
}
